﻿#ifndef List_h__
#define List_h__

/********************************************************************
	创建于:		2011/04/19
	创建于:		19:4:2011   21:49
	基本文件:	List
	文件扩展:	h
	作者:		王凯
	
	目的:		双端链表
*********************************************************************/

#include <stdio.h>

#ifndef NULL
#define NULL 0
#endif

template<typename Object>
class List
{
private:
	//节点数据结构	
	struct Node
	{
		Object Data;
		Node* Next;
		Node* Prev;

		Node(const Object& Data = Object(), Node* p = NULL, Node* n = NULL):
		Data(Data), Next(n), Prev(p)
		{}
	};

	int m_iSize;
	Node* m_pHead;
	Node* m_pTail;

	void init()
	{
		m_iSize = 0;
		m_pHead = new Node();
		m_pTail = new Node();
		m_pHead->Next = m_pTail;
		m_pTail->Prev = m_pHead;
	}

public:
	class Const_Iterator
	{
	protected:
		Node* m_pCurrent;
		
		Const_Iterator(Node* p):
		m_pCurrent(p){}

		Object& Retrieve()const{ return m_pCurrent->Data;}

	public:
		Const_Iterator():
		m_pCurrent(NULL){}

		//后置++
		Const_Iterator operator++(int)
		{
			Const_Iterator old = *this;
			++(*this);
			return old;
		}

		//前置++
		Const_Iterator& operator++()
		{
			m_pCurrent = m_pCurrent->Next;
			return *this;
		}

		//后置--
		Const_Iterator operator--(int)
		{
			Const_Iterator old = *this;
			--(*this);
			return old;
		}

		//前置--
		Const_Iterator& operator--()
		{
			m_pCurrent = m_pCurrent->Prev;
			return *this;
		}

		//实现解引用操作符重载
		Object& operator*() const
		{
			return Retrieve();
		}
		
		bool operator!=(const Const_Iterator& rhs)const
		{
			return !(*this == rhs);
		}

		bool operator==(const Const_Iterator& rhs)const
		{
			return m_pCurrent == rhs.m_pCurrent;
		}

		friend class List<Object>;
	};

	class Iterator : public Const_Iterator
	{
	protected:
		Iterator(Node* p): Const_Iterator(p)
		{}
	public:
		Iterator()
		{}

		Iterator& operator++()
		{
			m_pCurrent = m_pCurrent->Next;
			return *this;
		}

		Iterator operator++(int)
		{
			Iterator old = *this;
			++(*this);
			return old;
		}

		Iterator& operator--()
		{
			m_pCurrent = m_pCurrent->Prev;
			return *this;
		}

		Iterator operator--(int)
		{
			Iterator old = *this;
			--(*this);
			return old;
		}

		Object& operator*()
		{
			return Retrieve();
		}

		const Object& operator*()const
		{ return Const_Iterator::operator*(); }

		bool operator!=(const Iterator& rhs)
		{
			return !(*this == rhs);
		}

		bool operator==(const Iterator& rhs)
		{
			return m_pCurrent == rhs.m_pCurrent;
		}

		friend class List<Object>;
	};

	List()
	{ init();}

	~List()
	{
		clear();
		delete m_pHead;
		delete m_pTail;
	}
	List(const List& rhs)
	{
		init();
		*this = rhs;
	}

	const List& operator=(const List& rhs)
	{
		if( this == &rhs)
			return *this;
		clear();
		for(Const_Iterator itr = rhs.begin(); itr != rhs.end(); ++itr)
			push_back( *itr);
		return *this;
	}
	int size()const{ return m_iSize;}
	bool empty()const{ return size() == 0;}

	Iterator begin(){ return Iterator(m_pHead->Next);}
	Const_Iterator begin()const{ return Const_Iterator(m_pHead->Next);}
	Iterator end(){ return Iterator(m_pTail);}
	Const_Iterator end()const{ return Const_Iterator(m_pTail);}

	Object& front(){ return *begin();}
	const Object& front()const{ return *begin();}

	Object& back(){ return *--end();}
	const Object& back()const{ return *--end();}

	void push_back(const Object& x){ insert(end(), x);}
	void push_front(const Object& x){ insert(begin(), x);}
	void pop_back(){ erase(--end());}
	void pop_front(){ erase(begin());}

	void assign(Object& x, int n)
	{
		for(int i = 0; i < n; i++)
			push_back(x);
	}

	void clear()
	{
		while(!empty())
			pop_front();
	}

	Iterator insert(Iterator iter, const Object& n)
	{
		Node* p = iter.m_pCurrent;
		m_iSize++;
		/*
		p->Prev->Next = nwe Node(n, p->Prev, p);
		p->Prev = p->Prev->Next;
		return Iterator(p->Prev);
		*/
		return Iterator( p->Prev = p->Prev->Next = new Node(n, p->Prev, p));	
	}

	Iterator erase(Iterator iter)
	{
		Node* p = iter.m_pCurrent;
		Iterator retVal(p->Next);
		p->Prev->Next = p->Next;
		p->Next->Prev = p->Prev;
		delete p;
		m_iSize--;
		return retVal;
	}

	Iterator erase(Iterator start, Iterator end)
	{
		for(Iterator iter = start, iter != end;)
			iter = erase(iter);

		return end;
	}
};


#endif // List_h__
